package Offer;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class T07_buildTree {

    private Map<Integer, Integer> map = new HashMap<>();
    @Test
    public void test() {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
//        int[] preorder = {1, 2};
//        int[] inorder = {2, 1};
        TreeNode root = buildTree(preorder, inorder);
    }


//    --------------法1 递归 -----------------------------------
//    因为每个结点都要遍历一遍，所以时间复杂度为O(n),
//    需要创建哈希表，以及创建树，还有递归栈的深度，所以空间复杂度为O(h)+O(n)+O(n) ==O(n) (h<n)
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {  //使用hash表优化一下根节点下标的查找
            if (!map.containsKey(inorder[i])) {
                map.put(inorder[i], i);
            }
        }

        return build(preorder, inorder, 0, inorder.length - 1, 0);
    }

    /**
     * @param preorder
     * @param inorder
     * @param start    中序序列的左边界
     * @param end      中序序列的右边界
     * @param p        标记先序序列的根结点
     * @return
     */
    TreeNode build(int[] preorder, int[] inorder, int start, int end, int p) {
        if (start > end) {
            return null;
        }

        if (start == end) {
            return new TreeNode(inorder[start]);
        }

        //先通过先序序列找根结点,如何定位根结点？
        int val = preorder[p];
        TreeNode root = new TreeNode(val);

        //通过中序序列找根节点，以便划分左右子树
        /*int index = 0;  //index指向中序的根结点位置
        while (inorder[index] != val) {
            index++;
        }*/

        int index;
        index = map.get(val);

        int llen = index - start;  //左半区的长度

        root.left = build(preorder, inorder, start, index - 1, p + 1);
        root.right = build(preorder, inorder, index + 1, end, p + llen + 1);
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}